package main

// 给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：

// 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；
// 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。
// 返回 图中最大连通组件的大小 。


// 计算并查集的大小
type unionFind struct {
	// 并查集，包含一个数据
	parent []int   // 根节点的parent等于自己
	rank []int   // 使用秩可以加快检索
}

func newUninFind(n int) unionFind {
	parent := make([]int, n)
	for i:=range parent{
		parent[i]=i
	}
	return unionFind{
		parent: parent,
		rank: make([]int, n),
	}
}

// 定义并查集的函数，查找parent
func (u unionFind)find(x int) int {
	if u.parent[x] != x {
		// 迭代  更新parent
		u.parent[x] = u.find(u.parent[x])
	}
	return u.parent[x]
}

func (u unionFind) merge(x,y int) {
	x,y = u.find(x),u.find(y)
	if x==y {
		return 
	}
	if u.rank[x] > u.rank[y] {
		u.parent[y] = x
	} else if u.rank[x] < u.rank[y] {
		u.parent[x] = y 
	} else {
		u.parent[y] = x   // 
		u.rank[x] ++
	}
}

func largestComponentSize(nums []int) int {
	var res int
	m := 0 
	for _,num := range nums {
		m = max(m, num)
	}
	u := newUninFind(m+1)
	for _,num := range nums {
		for i:=2; i*i <=num ; i++ {
			if num%i ==0 {    // 因数关系
				u.merge(num, i)
				u.merge(num, num/i)
			}
		}
	}

	cnt := make([]int, m+1) 
	for _,num := range nums {
		rt := u.find(num)
		cnt[rt] ++
		res = max(res, cnt[rt])
	}
	return res
}

func max(a,b int) int {
	if b>a {
		return b
	}
	return a
}